# 计算数塔的最小路径和
def minimumTotal(triangle: list[list[int]]) -> int:
    n = len(triangle)
    # 创建备忘录
    dp = [[]] * n
    # 自下而上进行填表
    dp[-1] = triangle[-1]
    for i in range(n - 2, -1, -1):
        dp[i] = [t + min(dp[i + 1][j], dp[i + 1][j + 1]) for j, t in enumerate(triangle[i])]

    # 完成填表并返回结果
    return dp[0][0]

triangle = [[9],[13,16],[4,10,7],[9,11,6,13],[17,5,19,11,10]]
ans = minimumTotal(triangle)
print('最小路径和为:', ans)